package shu;

import utils.Utils;
/**
计数排序<br />
        * 思路：开辟新的空间，空间大小为max(source)<br />
        *      扫描source，将value作为辅助空间的下标，用辅助空间的改位置元素记录value的个数<br />
        *      如：9 7 5 3 1 ，helper=arr(10)<br />
        *      一次扫描，value为9，将helper[9]++，value为7，将helper[7]++……<br />
        *      如此这般之后，我们遍历helper，如果该位（index）的值为0，说明index不曾在source中出现<br />
        *      如果该位（index)的值为1，说明index在source中出现了1次，为2自然是出现了2次<br />
        *      遍历helper就能将source修复为升序排列<br />
        *      int[] helper = new int[maxOf(source)+1];
        *      for(int e : source)
        *        helper[e]++;
        *      k=0;
        *      for(i in 1...)
        *        while(helper[i]>0)
        *          source[k++] = i;
        *          helper[i]--;
        *
        * 时间复杂度： 扫描一次source，扫描一次helper，复杂度为N+k<br />
        * 空间复杂度：辅助空间k，k=maxOf(source)<br />
        * 非原址排序<br />
        * 稳定性：相同元素不会出现交叉，非原址都是拷来拷去<br />
        * 如果要优化一下空间，可以求minOf(source)，helper的长度位max-min+1，这样能短点<br />
 * */
public class _03计数排序 {
    public static void main(String[] args) {
        int[] a = {10,20,2,55,3,1,0};
        sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void sort(int[] a){
        int[] helper = new int[Utils.maxOf(a) + 1];
        for (int e : a) {
            helper[e] ++;
        }
        int current = 0;
        for (int i = 0 ; i< helper.length;i++){
            while (helper[i] >0){
                a[current++] = i;
                helper[i] --;
            }
        }
    }




}
